package offer;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

class MaxQueue {
    Queue<Integer> queue;
    Deque<Integer> maxDeque;

    public MaxQueue() {
        queue = new LinkedList<>();
        maxDeque = new LinkedList<>();
    }

    public int max_value() {
        return maxDeque.isEmpty() ? -1 : maxDeque.peek();
    }

    public void push_back(int value) {
        Integer v = value;
        queue.offer(v);
        while (!maxDeque.isEmpty() && maxDeque.peekLast() < value) {
            maxDeque.pollLast();
        }
        maxDeque.offer(v);
    }

    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }
        Integer t = queue.poll();
        if (t == maxDeque.peek()) {
            maxDeque.poll();
        }
        return t;
    }
}
